package binarySearch;

import java.util.Arrays;

/**
 * @program: algorithm
 * @description: 二分查找
 * @author: Yan.Zhang
 * @create: 2020-04-21 09:17
 **/
public class BinarySearch {


    /**
     * 传入的数组必须要有序。
     * 如果key存在于数组中，就返回其索引，否则就返回-1
     * 算法使用两个变量first和length，并保证如果key在数组中则一定在arr[first...length]中，
     * 然后方法进入一个循环，不断将数组的中间键(索引为mid)和被查找的key比较。如果被查找的key等于a[mid],返回mid;
     * 否则算法就将查找范围缩小一半，如果被查找的key小于a[mid]就继续在左半边查找，
     * 如果被查找的key大于a[mid]就继续在右半边查找。算法找到被查找的key或是查找范围为空时该过程结束。
     *
     * 10 11 12 16 18 23 27 33 38 44 51  -> 有序数组
     * first -> 0  length -> 10   key -> 18   mid -> 5 = 0 + (10-0) / 2
     *
     * 10 11 12 16 18
     * mid - > 4
     *
     *
     * @param key   要查找的值
     * @param arr   有序数组
     * @return
     */
    public static int runk(int key, int[] arr) {
        int first = 0;
        int length = arr.length - 1;
        while (first <= length) {
            //  被查找的数要么不存在。要么必然存在于arr[first...length]之中
            int mid = first + (length - first) / 2;
            if (key < arr[mid]) {
                length = mid - 1;
            } else if (key > arr[mid]) {
                first = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }


    public static void main(String[] args){

        int[] arr = {10,11,12, 16, 18, 23, 27, 33, 38, 44, 51};
        Arrays.sort(arr);
        System.out.println(runk(18,arr));
        //啊啊啊
        //22221121211212

        ///21321321
    }
}